Continuous tone images do not print well on most printing devices, so the image is usually printed as pattern of dots based on a grid. The grid consists of an array of halftone cells, each of which represents one section of continuous tone in the original image. When reproducing a halftoned image in this way using a digital recording device, a halftone cell consists of a plurality of device pixels. A portion of the display pixels of each halftone cell are turned black to form dots relatively larger or smaller to represent darker or lighter portions of the original continuous tone image. A dark halftone cell will have most of the pixels turned black, while a light halftone cell will have most of the pixels turned white. A complete grid of the original image is composed of many such halftone cells, each of which has an independent density of displayed pixels and therefore a different apparent darkness when viewed from a distance.
A common prior art method of selecting which dots in each halftone cell to turn black works as follows. For a given halftone cell, the original image is sampled at each display pixel location in the halftone cell to obtain a gray value. This gray value is represented digitally as a number in a fixed range, typically 0 to 255. The gray value is then compared to a threshold value in the same range and the display pixel is turned white if the gray value is greater than the threshold value, or otherwise black. The threshold values, in turn, are supplied by means of a threshold array which contains a separate threshold value for each pixel in the halftone cell, and is computed ahead of time prior to processing the image. This process is carried out for each halftone cell of the image.
This prior art method works best when the same threshold array can be used for all halftone cells in the image. One advantage is that only one threshold array need be calculated and stored for the entire image. Another advantage is that a gray area of a given intensity will produce the same size and shape dots no matter where it occurs in the image. However, in order for this method to work, the set of display pixels corresponding to each halftone cell in the image must be exactly the same size and shape as the set of display pixels corresponding to any other halftone cell. This requirement is most often met by requiring the halftone cells to be parallelograms whose corners all fall exactly on integral coordinates in display pixel space. U.S. Pat. No. 4,185,304, incorporated herein by reference, shows one embodiment of this method.
One problem with the above method is that the number of different halftone screens that can be reproduced is limited by the requirement that the corners of the halftone cells must fall on integer coordinates in display pixel space. For example, screens rotated through the 15.degree. or 75.degree. commonly used in color printing cannot accurately be reproduced by this method. This shortcoming is addressed in co-pending U.S. patent application Ser. No. 07/846,754, incorporated herein by reference, assigned to the same assignee as this invention, where it is shown how a threshold array that consists of multiple halftone cells can be used to increase the number of available halftone screens to the point where any arbitrary screen can be approximated to within adequate tolerances.
Unfortunately the multiple halftone cells in such a threshold array generally have to be of differing shapes and sizes when those halftone cells are represented by display pixels. This means that the dots produced by the different halftone cells may also be of different shapes and sizes even when they represent the same gray value. Depending on the degree of difference in the size and shape of halftone dots, these differences may or may not be visible to the human eye. When these differences are visible, one sees a mottled variation in gray intensity in the form of repeating spots or bands where the original image contained only a constant gray. Such patterns do not faithfully reproduce the original image and are thus undesirable.
The following terms are defined for clarity. An ideal halftone cell, or ideal cell for short, will be a halftone cell, such as is discussed above, which is an element of the halftone grid consisting of an area bounded by a rotated square or a parallelogram. In contrast, a digital halftone cell, or digital cell for short, will be a set of pixels used to approximate an ideal halftone cell. Thus, each digital halftone cell is associated with the specific ideal halftone cell which it approximates. Also, in keeping with the above mentioned co-pending U.S. patent application Ser. No. 07/846,754, incorporated herein by reference, a threshold array that consists of multiple halftone cells will be referred to as "supertile".
In the above prior art method of generating a supertile, a digital halftone cell consists of all the pixels in the supertile whose geometric centers fall within the associated ideal cell. This method creates digital halftone cells of satisfactory consistency for certain halftone screens, but for other screens an unsatisfactory variation in digital cell size resulted. These variations occur because, although each ideal cell has the same shape, its placement with respect to the pixel grid varies by fractional amounts of pixels so that in some cases, more pixel centers would fall inside an ideal cell and in other cases fewer pixel centers would fall inside an ideal cell. The resulting variations in the size of the digital halftone cells cause corresponding variations in the size of halftone dots when certain values of gray are reproduced. This will be known as the "unequal cell size problem".
It is an object of the present invention to correct the unequal cell size problem.
The present invention describes a method for the creation of digital halftone cells from among the pixels in a supertile so as to make all such digital halftone cells as nearly the same size as possible, while at the same time still faithfully approximating the shape of the associated ideal cells.